package org.geotools.geosearch;

import DirectedGraph.MyFeatureGraphGenerator;
import com.vividsolutions.jts.linearref.LinearLocation;


import org.geotools.data.simple.SimpleFeatureIterator;
import org.geotools.factory.CommonFactoryFinder;
import org.geotools.geometry.jts.ReferencedEnvelope;
import org.geotools.graph.traverse.standard.AStarIterator.AStarNode;
import org.geotools.styling.StyleFactory;
import org.opengis.feature.type.GeometryDescriptor;
import org.opengis.filter.Filter;
import org.opengis.filter.FilterFactory2;

import com.vividsolutions.jts.geom.MultiPolygon;
import com.vividsolutions.jts.geom.Polygon;



import java.util.Collection;
import org.geotools.geometry.DirectPosition2D;
import com.vividsolutions.jts.geom.Coordinate;
import com.vividsolutions.jts.geom.Envelope;
import java.util.Iterator;

import java.util.logging.Level;
import java.util.logging.Logger;
import org.geotools.data.simple.SimpleFeatureCollection;
import org.geotools.data.simple.SimpleFeatureSource;
import org.opengis.feature.Feature;
import com.vividsolutions.jts.geom.Geometry;
import com.vividsolutions.jts.geom.GeometryFactory;
import org.opengis.referencing.crs.CoordinateReferenceSystem;

import org.opengis.feature.simple.SimpleFeature;

import com.vividsolutions.jts.geom.LineString;
import com.vividsolutions.jts.geom.MultiLineString;
import com.vividsolutions.jts.geom.Point;
import com.vividsolutions.jts.index.SpatialIndex;
import com.vividsolutions.jts.index.strtree.STRtree;
import com.vividsolutions.jts.linearref.LocationIndexedLine;
import java.awt.geom.Point2D;
import java.beans.FeatureDescriptor;
import java.io.File;
import java.io.IOException;
import java.io.StringWriter;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.UUID;
import javax.swing.JOptionPane;
import org.geotools.data.DataStore;
import org.geotools.data.DataStoreFinder;
import org.geotools.data.DataUtilities;
import org.geotools.data.FeatureSource;
import org.geotools.data.FileDataStore;
import org.geotools.data.FileDataStoreFinder;
import org.geotools.data.ServiceInfo;
import org.geotools.data.memory.MemoryFeatureCollection;
import org.geotools.data.postgis.PostgisNGDataStoreFactory;
import org.geotools.factory.GeoTools;
import org.geotools.feature.DefaultFeatureCollection;
import org.geotools.feature.FeatureCollections;
import org.geotools.feature.FeatureIterator;
import org.geotools.feature.simple.SimpleFeatureBuilder;
import org.geotools.filter.FilterFactory;
import org.geotools.filter.FilterFactoryFinder;
import org.geotools.filter.LiteralExpression;
import org.geotools.geojson.feature.FeatureJSON;
import org.geotools.geometry.jts.JTSFactoryFinder;
import org.geotools.graph.build.line.DirectedLineStringGraphGenerator;
import org.geotools.graph.path.AStarShortestPathFinder;
import org.geotools.graph.path.DijkstraShortestPathFinder;
import org.geotools.graph.path.Path;
import org.geotools.graph.structure.DirectedNode;
import org.geotools.graph.structure.Edge;
import org.geotools.graph.structure.Node;
import org.geotools.graph.structure.basic.BasicDirectedEdge;
import org.geotools.graph.structure.basic.BasicDirectedGraph;
import org.geotools.graph.structure.basic.BasicDirectedNode;

import org.geotools.graph.traverse.standard.AStarIterator.AStarFunctions;
import org.geotools.graph.traverse.standard.DijkstraIterator;
import org.geotools.graph.traverse.standard.DirectedDijkstraIterator;
import org.geotools.swing.JMapPane;
import org.geotools.swing.data.JDataStoreWizard;
import org.geotools.swing.wizard.JWizard;
import org.geotools.util.NullProgressListener;
import org.opengis.feature.FeatureVisitor;
import org.opengis.feature.simple.SimpleFeatureType;
import org.opengis.feature.type.Name;
import org.opengis.filter.expression.PropertyName;

/**
 * Класс поиска
 * @author oleg
 */
public class Guide {

    public enum ConnectionType {

        DB, FILE
    }

    public enum Algorithm {

        DIJKSTRA, ASTAR
    }
    private SimpleFeatureSource featureSource;
    //это узлы для определения направлений
    private SimpleFeatureSource featureSourceNodes = null;
    private CoordinateReferenceSystem oldCRS;
    private CoordinateReferenceSystem newCRS;
    private CoordinateReferenceSystem currentCRS;
    private SimpleFeature featureStartOld;
    private SimpleFeature featureFinishOld;
    private SimpleFeature simpleFeatureStart[];
    private SimpleFeature simpleFeatureFinish[];
    private int add = 0;
    private int searchType;
    private SimpleFeature inmemory[];
    private SimpleFeatureCollection inmemoryCollection;
    private boolean useRoadQuality = false;
    private boolean useSemaphores = false;
    private SimpleFeatureCollection memSemaphoresCollection = null;
    private double semaphoreKoeff = 10;
    private SpatialIndex index;
    private String geometryAttributeName;
    private GeomType geometryType;
    private JMapPane pane;
    private StyleFactory sf = CommonFactoryFinder.getStyleFactory(null);
    private FilterFactory2 ff = CommonFactoryFinder.getFilterFactory2(null);
    private Algorithm algorithm = Algorithm.DIJKSTRA;
    private String roadTypeProp = "TYPE";
    private String onewayProp = "ONEWAY";
    private String timeProp = "TIME";

    public Algorithm getAlgorithm() {
        return algorithm;
    }

    public void setAlgorithm(Algorithm algorithm) {
        this.algorithm = algorithm;
    }

    public SimpleFeatureCollection getMemSemaphoresCollection() {
        return memSemaphoresCollection;
    }

    public double getSemaphoreKoeff() {
        return semaphoreKoeff;
    }

    public void setSemaphoreKoeff(double semaphoreKoeff) {
        this.semaphoreKoeff = semaphoreKoeff;
    }

    public boolean isUseRoadQuality() {
        return useRoadQuality;
    }

    public void setUseRoadQuality(boolean useRoadQuality) {
        this.useRoadQuality = useRoadQuality;
    }

    public boolean isUseSemaphores() {
        return useSemaphores;
    }

    public void setSemaphoresSource(SimpleFeatureSource semaphoresSource) {
        try {
            memSemaphoresCollection = DataUtilities.collection(semaphoresSource.getFeatures());
        } catch (IOException ex) {
            Logger.getLogger(Guide.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    public void setUseSemaphores(boolean useSemaphores) {
        this.useSemaphores = useSemaphores;
    }

    private SimpleFeature[] getSimpleFeatureFinish() {
        return simpleFeatureFinish;
    }

    private SimpleFeature[] getSimpleFeatureStart() {
        return simpleFeatureStart;
    }

    private void setSimpleFeatureFinish(SimpleFeature[] simpleFeatureFinish) {
        this.simpleFeatureFinish = simpleFeatureFinish;
    }

    private void setSimpleFeatureStart(SimpleFeature[] simpleFeatureStart) {
        this.simpleFeatureStart = simpleFeatureStart;
    }

    private SimpleFeature getFeatureFinishOld() {
        return featureFinishOld;
    }

    private SimpleFeature getFeatureStartOld() {
        return featureStartOld;
    }

    private void setFeatureFinishOld(SimpleFeature featureFinishOld) {
        this.featureFinishOld = featureFinishOld;
    }

    /**
     *
     * @param a хранит информацию о разделении feature
     */
    private void setAdd(int a) {
        this.add = a;
    }

    private void setFeatureStartOld(SimpleFeature featureStartOld) {
        this.featureStartOld = featureStartOld;
    }

    /**
     * Конструктор. Пока oldCRS и newCRS не учитываются.
     * @param featureSource
     * @param oldCRS
     * @param newCRS
     * @param searchType =0 тип поиска (направленный граф)
     */
    public Guide(SimpleFeatureSource featureSource, CoordinateReferenceSystem oldCRS, CoordinateReferenceSystem newCRS, int searchType) {
        try {
            this.featureSource = featureSource;
            this.oldCRS = oldCRS;
            this.newCRS = newCRS;
            this.searchType = searchType;
            SimpleFeatureCollection var1 = featureSource.getFeatures();
            inmemoryCollection = DataUtilities.collection(var1);
            this.inmemory = (SimpleFeature[]) var1.toArray();


            //определяем тип геометрии
            setGeometry(featureSource);

            //for snapping
            index = new STRtree();
            inmemoryCollection.accepts(new FeatureVisitor() {

                public void visit(Feature feature) {
                    SimpleFeature simpleFeature = (SimpleFeature) feature;
                    Geometry geom = (MultiLineString) simpleFeature.getDefaultGeometry();
                    Envelope bounds = geom.getEnvelopeInternal();
                    if (bounds.isNull()) {
                        return; // must be empty geometry?
                    }
                    index.insert(bounds, new LocationIndexedLine(geom));
                }
            }, new NullProgressListener());

        } catch (IOException ex) {
            Logger.getLogger(Guide.class.getName()).log(Level.SEVERE, null, ex);
        }
    }
    
    /**
     * Use this if features are in PostGRES database. All you need is database parameters. Below is example.
     *       Map params = new HashMap();
     *       params.put("namespace", "leeds");
     *       params.put("dbtype", "postgis");
     *       params.put("host", "localhost");
     *       params.put("port", "5432");
     *       params.put("database", "gis");
     *       params.put("user", "oleg");
     *       params.put("passwd", "");
     *       Guide guide = new Guide(params);
     * @param params
     */
    static public Guide fromDB(Map params) {
        Guide guide = new Guide(ConnectionType.DB, params);
        return guide;
    }

    static public Guide fromFile(String filepath) {
        Guide guide = new Guide(ConnectionType.FILE, filepath);
        return guide;
    }

    private void initDB(Map params) {
        try {
            DataStore dataStore = null;

            try {
                dataStore = DataStoreFinder.getDataStore(params);
            } catch (IOException ex) {
                Logger.getLogger(Guide.class.getName()).log(Level.SEVERE, null, ex);
            }
            if (dataStore == null) {
                JOptionPane.showMessageDialog(null, "Could not connect - check parameters");
            }
            ServiceInfo info = dataStore.getInfo();
            List<Name> names = null;
            try {
                names = dataStore.getNames();
            } catch (IOException ex) {
                Logger.getLogger(Guide.class.getName()).log(Level.SEVERE, null, ex);
            }
            SimpleFeatureType schema = dataStore.getSchema(names.get(1));
            featureSource = dataStore.getFeatureSource(names.get(1));
            this.oldCRS = null;
            this.newCRS = null;
            this.searchType = 0;
            if (featureSource == null) {
                System.out.println("featureSource=null");
            }
            SimpleFeatureBuilder sfb = new SimpleFeatureBuilder(schema);

            SimpleFeatureCollection features = featureSource.getFeatures();
            SimpleFeatureIterator iterator = features.features();
            inmemoryCollection = new MemoryFeatureCollection(schema);
            try {
                while (iterator.hasNext()) {
                    SimpleFeature feature = iterator.next();
                    //Geometry geom = (Geometry) feature.getDefaultGeometry();
                    //Point centroid = geom.getCentroid();
                    //System.out.println(centroid);
                    sfb.init(feature);
                    SimpleFeature copyFeature = sfb.buildFeature(feature.getID());
                    inmemoryCollection.add(copyFeature);

                }
            } finally {
                iterator.close(); // IMPORTANT
            }
            System.out.println("copied");
            this.inmemory = (SimpleFeature[]) features.toArray();

            //определяем тип геометрии
            setGeometry(featureSource);

            //for snapping
            index = new STRtree();
            inmemoryCollection.accepts(new FeatureVisitor() {

                public void visit(Feature feature) {
                    SimpleFeature simpleFeature = (SimpleFeature) feature;
                    Geometry geom = (MultiLineString) simpleFeature.getDefaultGeometry();
                    Envelope bounds = geom.getEnvelopeInternal();
                    if (bounds.isNull()) {
                        return; // must be empty geometry?
                    }
                    index.insert(bounds, new LocationIndexedLine(geom));
                }
            }, new NullProgressListener());
            dataStore.dispose();

        } catch (IOException ex) {
            Logger.getLogger(Guide.class.getName()).log(Level.SEVERE, null, ex);
        }
    }

    private void initFile(String filepath) {
        FileDataStore store;


            try {
                if (filepath == null) {
                    filepath = "improvedmap/improved004.shp";
                }
                File sourceFile = new File(filepath);
                if (sourceFile == null) {
                    System.out.println("файл не найден");
                    return;
                }
                store = FileDataStoreFinder.getDataStore(sourceFile);
                featureSource = store.getFeatureSource();
            } catch (IOException ex) {
                Logger.getLogger(Guide.class.getName()).log(Level.SEVERE, null, ex);
            }
            try {
                this.oldCRS = null;
                this.newCRS = null;
                this.searchType = 0;
                if (featureSource == null) {
                    System.out.println("featureSource=null");
                }
                SimpleFeatureCollection var1 = featureSource.getFeatures();
                inmemoryCollection = DataUtilities.collection(var1);
                //inmemoryCollection=features;
                //inmemoryCollection = FeatureCollections.newCollection();
                this.inmemory = (SimpleFeature[]) var1.toArray();
                //определяем тип геометрии
                setGeometry(featureSource);
                //for snapping
                index = new STRtree();
                System.out.println("Slurping in features ...");
                var1.accepts(new FeatureVisitor() {

                    @Override
                    public void visit(Feature feature) {
                        SimpleFeature simpleFeature = (SimpleFeature) feature;
                        Geometry geom = (MultiLineString) simpleFeature.getDefaultGeometry();
                        Envelope bounds = geom.getEnvelopeInternal();
                        if (bounds.isNull()) {
                            return; // must be empty geometry?
                        }
                        index.insert(bounds, new LocationIndexedLine(geom));
                    }
                }, new NullProgressListener());
            } catch (IOException ex) {
                Logger.getLogger(Guide.class.getName()).log(Level.SEVERE, null, ex);
            }

/*


        
        try {
        if (filepath == null) {
        filepath = "improvedmap/improved004.shp";
        }
        File sourceFile = new File(filepath);
        if (sourceFile == null) {
        System.out.println("файл не найден");
        return;
        }
        store = FileDataStoreFinder.getDataStore(sourceFile);
        featureSource = store.getFeatureSource();
        } catch (IOException ex) {
        Logger.getLogger(Guide.class.getName()).log(Level.SEVERE, null, ex);
        }
        try {
        this.oldCRS = null;
        this.newCRS = null;
        this.searchType = 0;
        if (featureSource == null) {
        System.out.println("featureSource=null");
        }
        SimpleFeatureCollection var1 = featureSource.getFeatures();

        inmemoryCollection = DataUtilities.collection(var1);
        //inmemoryCollection=features;
        //inmemoryCollection = FeatureCollections.newCollection();
        this.inmemory = (SimpleFeature[]) var1.toArray();
        //определяем тип геометрии
        setGeometry(featureSource);
        //for snapping
        index = new STRtree();
        System.out.println("Slurping in features ...");
        var1.accepts(new FeatureVisitor() {

        @Override
        public void visit(Feature feature) {
        SimpleFeature simpleFeature = (SimpleFeature) feature;
        Geometry geom = (MultiLineString) simpleFeature.getDefaultGeometry();
        Envelope bounds = geom.getEnvelopeInternal();
        if (bounds.isNull()) {
        return; // must be empty geometry?
        }
        index.insert(bounds, new LocationIndexedLine(geom));
        }
        }, new NullProgressListener());
        } catch (IOException ex) {
        Logger.getLogger(Guide.class.getName()).log(Level.SEVERE, null, ex);
        }
     */
    }

    public Guide(ConnectionType conType, Object param) {
        switch(conType)
        {
            case DB:
                initDB((Map)param);
                break;
            case FILE:
                initFile((String)param);
                break;
        }
    }

    private boolean isPointOnGeometry(double x, double y, Geometry geom) {
        double distance = Double.MAX_VALUE;
        Point2D.Double pointOnLine = new Point2D.Double();
        Coordinate[] line = geom.getCoordinates();

        for (int i = 0; i < line.length - 1; i++) {

            double x0 = line[i].x;
            double y0 = line[i].y;
            double x1 = line[i + 1].x;
            double y1 = line[i + 1].y;
            double x_min, y_min, x_max, y_max;
            if (x0 <= x1) {
                x_min = x0;
                x_max = x1;
            } else {
                x_min = x1;
                x_max = x0;
            }
            if (y0 <= y1) {
                y_min = y0;
                y_max = y1;
            } else {
                y_min = y1;
                y_max = y0;
            }
            if ((x <= x_max) && (x >= x_min) && (y <= y_max) && (y >= y_min)) {
                double a = y0 - y1;
                double b = x1 - x0;
                double c = x0 * y1 - x1 * y0;
                double dist = Math.abs((x * a + y * b + c) / Math.pow(a * a + b * b, 0.5));



                if ((dist < distance) && (Point2D.distance(x, y, x1, y1) > dist) && (Point2D.distance(x, y, x0, y0) > dist)) {
                    distance = dist;

                    double d = a * y - b * x;
                    double det = -a * a - b * b;
                    double det1 = a * c + b * d;
                    double det2 = -a * d + b * c;

                    pointOnLine.setLocation(det1 / det, det2 / det);
                    return true;
                }
            }
        }


        return false;
    }

    /**
     * Возвращает расстояние между точкой с координатами (x, y) и
     * отрезком прямой, заданной двумя точками p1 и p2.
     * @param x координата точки
     * @param y координата точки
     * @param p1 точка прямой
     * @param p2 точка прямой
     * @return
     */
    static private double pointDistanceFromTheLine(double x, double y, DirectPosition2D p1, DirectPosition2D p2) {
        double distance = 9999999;
        double x0 = p1.x;
        double y0 = p1.y;
        double x1 = p2.x;
        double y1 = p2.y;
        double x_min, y_min, x_max, y_max;
        if (x0 <= x1) {
            x_min = x0;
            x_max = x1;
        } else {
            x_min = x1;
            x_max = x0;
        }
        if (y0 <= y1) {
            y_min = y0;
            y_max = y1;
        } else {
            y_min = y1;
            y_max = y0;
        }
        if ((x <= x_max) && (x >= x_min) && (y <= y_max) && (y >= y_min)) {
            double a = y0 - y1;
            double b = x1 - x0;
            double c = x0 * y1 - x1 * y0;
            double dist = Math.abs((x * a + y * b + c) / Math.pow(a * a + b * b, 0.5));

            if ((dist < distance) && (Point2D.distance(x, y, x1, y1) > dist) && (Point2D.distance(x, y, x0, y0) > dist)) {
                return distance = dist;
            }
        }
        return 9999999;
    }

    /**
     * Возвращает true, если точка с координатами (x, y) принадлежит
     * отрезку прямой, заданному двумя точками p1 и p2.
     * @param x координата точки
     * @param y координата точки
     * @param p1 точка прямой
     * @param p2 точка прямой
     * @return
     */
    static private boolean pointIsOnTheLine(double x, double y, DirectPosition2D p1, DirectPosition2D p2) {
        if (pointDistanceFromTheLine(x, y, p1, p2) < 0.01) {
            return true;
        }
        return false;
    }

    /**
     * Возвращает true, если точка с координатами (x, y) принадлежит
     * отрезку прямой, заданному двумя точками p1 и p2.
     * @param x координата точки
     * @param y координата точки
     * @param p1 точка прямой
     * @param p2 точка прямой
     * @return
     */
    private static boolean pointIsOnTheLine(double x, double y, Coordinate coordinate1, Coordinate coordinate2) {
        if (pointDistanceFromTheLine(x, y, new DirectPosition2D(coordinate1.x, coordinate1.y), new DirectPosition2D(coordinate2.x, coordinate2.y)) < 0.1) {
            return true;
        }
        return false;
    }

    /**
     * splitFeature разбивает feature на две части точкой point
     * @param point
     * @param feature
     * @return
     */
    static private SimpleFeature[] splitFeature(DirectPosition2D point, SimpleFeature feature) {
        double x = point.x;
        double y = point.y;
        SimpleFeature duplicate = (SimpleFeature) DataUtilities.duplicate(feature);
        //SimpleFeature duplicate = (SimpleFeature) DataUtilities.reType(feature.getFeatureType(), feature);
        SimpleFeature duplicate1 = (SimpleFeature) DataUtilities.duplicate(feature);

        SimpleFeatureBuilder builder = new SimpleFeatureBuilder(duplicate.getFeatureType());
        builder.init(feature);
        duplicate = builder.buildFeature(UUID.randomUUID().toString().substring(0, 6));
        builder.init(feature);
        duplicate1 = builder.buildFeature(UUID.randomUUID().toString().substring(0, 6));

        Geometry geom = (MultiLineString) duplicate.getDefaultGeometry();
        Coordinate[] points = geom.getCoordinates();
        int pointNumber = -1; //точка клика лежит в списке после pointNumber.
        for (int i = 0; i < points.length - 1; i++) {
            if (pointIsOnTheLine(point.x, point.y, points[i], points[i + 1])) {
                pointNumber = i;
            }
        }

        if (pointNumber == -1) {
            pointNumber = 0;
            //ну если не удалось развбить, разбиваем так:
            double sums[] = new double[points.length - 1];
            for (int i = 0; i < points.length - 1; i++) {
                sums[i] = point.distance(points[i].x, points[i].y) + point.distance(points[i + 1].x, points[i + 1].y);
            }
            double min = sums[0];
            for (int i = 0; i < points.length - 1; i++) {
                if (min > sums[i]) {
                    min = sums[i];
                    pointNumber = i;
                }
            }
        }
        Coordinate[] points1 = new Coordinate[pointNumber + 2];
        Coordinate[] points2 = new Coordinate[points.length - pointNumber];
        System.arraycopy(points, 0, points1, 0, pointNumber + 1);
        points1[pointNumber + 1] = new Coordinate();
        points1[pointNumber + 1].x = x;
        points1[pointNumber + 1].y = y;
        System.arraycopy(points, pointNumber + 1, points2, 1, points.length - pointNumber - 1);
        points2[0] = new Coordinate();
        points2[0].x = x;
        points2[0].y = y;
        GeometryFactory geometryFactory = JTSFactoryFinder.getGeometryFactory(null);
        LineString line = geometryFactory.createLineString(points1);
        LineString line1 = geometryFactory.createLineString(points2);
        duplicate.setDefaultGeometry(line);
        duplicate1.setDefaultGeometry(line1);

        SimpleFeature[] RETURN = new SimpleFeature[2];
        RETURN[0] = duplicate;
        RETURN[1] = duplicate1;
        return RETURN;
    }

    class Snap {

        public Point2D.Double point;
        public long id;

        public Snap(Point2D.Double point, long id) {
            this.point = point;
            this.id = id;
        }
    }

    /**
     * Функция проецирует координаты клика мыши на дорожную сеть
     * @param point Координаты клика мыши
     * @return
     */
    private Snap snap(Point2D point) {
        Coordinate pt = new Coordinate(point.getX(), point.getY());
        Envelope search = new Envelope(pt);
        long id = -1;
        int count = 1;

        //расширяем конверт, если не нашли к чему привязывать
        while ((id == -1) && (count < 50)) {
            search.expandBy(10 * count);

            ReferencedEnvelope bbox = new ReferencedEnvelope(
                    search,
                    oldCRS);
            Filter filter = ff.intersects(ff.property(geometryAttributeName), ff.literal(bbox));
            SimpleFeatureCollection selectedFeatures =
                    inmemoryCollection.subCollection(filter);

            if (selectedFeatures.size() > 0) {
                Snap snaps[] = new Snap[selectedFeatures.size()];
                SimpleFeatureIterator iter = selectedFeatures.features();
                int j = 0;
                while (iter.hasNext()) {
                    SimpleFeature feature = iter.next();
                    Object value = feature.getProperty("ID").getValue();
                    if (value instanceof Double) {
                        double v = (Double) (feature).getProperty("ID").getValue();
                        id = Math.round(v);
                    } else {
                        id = (Long) (feature).getProperty("ID").getValue();
                    }
                    LocationIndexedLine line = new LocationIndexedLine((Geometry) feature.getDefaultGeometry());
                    LinearLocation here = line.project(pt);
                    Coordinate c = line.extractPoint(here);
                    Snap snap = new Snap(new Point2D.Double(c.x, c.y), id);
                    snaps[j] = snap;
                    j++;
                }
                iter.close();
                //выбираем самую близкую точку
                double minDistance = snaps[0].point.distance(point);
                Snap snap = snaps[0];
                for (int i = 0; i < j; i++) {
                    if (minDistance > snaps[i].point.distance(point)) {
                        minDistance = snaps[i].point.distance(point);
                        snap = snaps[i];
                    }
                }
                return snap;
            }
            count++;
        }
        if (id == -1) {
            return null;
        }

        List<LocationIndexedLine> hits = index.query(search);
        Coordinate c = null;
        if (hits.size() > 0) {
            LinearLocation here = hits.get(0).project(pt);
            c = hits.get(0).extractPoint(here);
            Snap snap = new Snap(new Point2D.Double(c.x, c.y), id);
            return snap;
        }
        return null;
    }

    public String guidanceJSON(double x1, double y1, double x2, double y2) {
        Path path = guidance(new Point2D.Double(x1, y1), new Point2D.Double(x2, y2));
        SimpleFeatureCollection features = FeatureCollections.newCollection();
        for (Iterator e = path.getEdges().iterator(); e.hasNext();) {
            Edge edge = (Edge) e.next();
            SimpleFeature pathFeature = (SimpleFeature) edge.getObject();
            features.add(pathFeature);
        }
        String json = null;
        try {
            FeatureJSON fjson = new FeatureJSON();
            StringWriter writer = new StringWriter();
            fjson.writeFeatureCollection(features, writer);
            json = writer.toString();

        } catch (IOException ex) {
            Logger.getLogger(Guide.class.getName()).log(Level.SEVERE, null, ex);
        }
        System.out.println("json finished");
        return json;
    }

    public String guidanceJSONMultiple(double x[]) {
        if (x.length < 4) {
            System.out.println("less then 2 points");
            return null;
        }
        DirectPosition2D points[] = new DirectPosition2D[x.length / 2];
        for (int i = 0; i < x.length / 2; i++) {
            points[i] = new DirectPosition2D(x[2 * i], x[2 * i + 1]);
        }
        DefaultRouteFactory dfr = new DefaultRouteFactory(this);
        SimpleFeatureCollection features =
                dfr.createPathSFC(points, AbstractRouteFactory.OrderType.ORDERPLEASE);
        String json = null;
        try {
            FeatureJSON fjson = new FeatureJSON();
            StringWriter writer = new StringWriter();
            fjson.writeFeatureCollection(features, writer);
            json = writer.toString();
        } catch (IOException ex) {
            Logger.getLogger(Guide.class.getName()).log(Level.SEVERE, null, ex);
        }
        return json;
    }

    public Point2D.Double[] guidanceReturnArray(double x1, double y1, double x2, double y2) {
        return guidanceReturnArray(new Point2D.Double(x1, y1), new Point2D.Double(x2, y2));
    }

    public Point2D.Double[] guidanceReturnArray(Point2D start, Point2D finish) {
        //очистка всяких переменных
        setAdd(0);

        //snapping
        Snap snap1 = snap(start);
        Snap snap2 = snap(finish);
        if ((snap1 == null) || (snap2 == null)) {
            Exception e;
            System.out.println("Точки не определены " + (Math.random() * 100));
            return null;
        }
        Path path = guidance(snap1.point, snap2.point, snap1.id, snap2.id);
        LinkedList<Point2D.Double> list = new LinkedList<Point2D.Double>();
        for (Iterator e = path.getEdges().iterator(); e.hasNext();) {
            Edge edge = (Edge) e.next();
            SimpleFeature pathFeature = (SimpleFeature) edge.getObject();
            Object defaultGeometry = pathFeature.getDefaultGeometry();
            if (defaultGeometry instanceof MultiLineString) {
                MultiLineString geom = (MultiLineString) defaultGeometry;
                Coordinate[] coordinates = geom.getCoordinates();
                for (int i = 0; i < coordinates.length; i++) {
                    list.add(new Point2D.Double(coordinates[i].x, coordinates[i].y));
                }
            }
        }
        Point2D.Double[] points = new Point2D.Double[list.size()];
        list.toArray(points);
        return points;
    }

    /**
     * Метод возвращает путь. Метод принимает только два аргумента - точку старта и точку финиша.
     * @param start
     * @param finish
     * @return
     */
    public Path guidance(Point2D start, Point2D finish) {

        //очистка всяких переменных
        setAdd(0);

        //snapping
        Snap snap1 = snap(start);
        Snap snap2 = snap(finish);
        if ((snap1 == null) || (snap2 == null)) {
            Exception e;
            System.out.println("Точки не определены " + (Math.random() * 100));
            return null;
        }

        Path original = guidance(snap1.point, snap2.point, snap1.id, snap2.id);
        Path path = new Path();

        SimpleFeatureCollection features = FeatureCollections.newCollection();
        SimpleFeature feature = null;
        boolean first = true;
        Edge first_edge = null;
        Edge last_edge = null;
        for (Iterator e = original.getEdges().iterator(); e.hasNext();) {
            Edge edge = (Edge) e.next();
            if (first) {
                first_edge = edge;
                first = false;
            }
            SimpleFeature pathFeature = (SimpleFeature) edge.getObject();
            features.add(pathFeature);
            if (!e.hasNext()) {
                feature = pathFeature;
                last_edge = edge;
            }
        }

        SimpleFeatureBuilder builder = new SimpleFeatureBuilder(feature.getFeatureType());

        builder.init(feature);
        SimpleFeature feature1 = builder.buildFeature(UUID.randomUUID().toString().substring(0, 6));
        Coordinate[] points1 = new Coordinate[2];
        points1[0] = new Coordinate(start.getX(), start.getY());
        points1[1] = new Coordinate(snap1.point.getX(), snap1.point.getY());
        GeometryFactory geometryFactory = JTSFactoryFinder.getGeometryFactory(null);
        LineString line = geometryFactory.createLineString(points1);
        feature1.setDefaultGeometry(line);
        feature1.setAttribute(roadTypeProp, "wow");
        feature1.setAttribute("LENGTH", start.distance(snap1.point));

        SimpleFeature feature2 = builder.buildFeature(UUID.randomUUID().toString().substring(0, 6));
        Coordinate[] points2 = new Coordinate[2];
        points2[1] = new Coordinate(finish.getX(), finish.getY());
        points2[0] = new Coordinate(snap2.point.getX(), snap2.point.getY());
        GeometryFactory geometryFactory2 = JTSFactoryFinder.getGeometryFactory(null);
        LineString line2 = geometryFactory2.createLineString(points2);
        feature2.setDefaultGeometry(line2);
        feature2.setAttribute(roadTypeProp, "wow");
        feature2.setAttribute("LENGTH", finish.distance(snap2.point));

        BasicDirectedNode node11 = new BasicDirectedNode();
        BasicDirectedEdge edge1 = new BasicDirectedEdge(node11, (DirectedNode) original.getFirst());
        node11.addIn(edge1);
        node11.addOut(edge1);
        ((DirectedNode) first_edge.getNodeA()).addIn(edge1);
        ((DirectedNode) first_edge.getNodeA()).addOut(edge1);
        edge1.setObject(feature1);

        BasicDirectedNode node2 = new BasicDirectedNode();
        BasicDirectedEdge edge2 = new BasicDirectedEdge((DirectedNode) original.getLast(), node2);
        node2.addIn(edge2);
        node2.addOut(edge2);
        ((DirectedNode) last_edge.getNodeB()).addOut(edge2);
        ((DirectedNode) last_edge.getNodeB()).addIn(edge2);
        edge2.setObject(feature2);


        path.addEdge(edge1);
        for (Iterator e = original.getEdges().iterator(); e.hasNext();) {

            Edge edge = (Edge) e.next();

            path.addEdge(edge);
            SimpleFeature pathFeature = (SimpleFeature) edge.getObject();
            features.add(pathFeature);
            if (!e.hasNext()) {
                feature = pathFeature;
            }
        }
        path.addEdge(edge2);

        return path;


    }

    /**
     * Метод возвращает путь.
     * @param start
     * @param finish
     * @param idStart
     * @param idFinish
     * @return
     */
    public Path guidance(Point2D start, Point2D finish, long idStart, long idFinish) {
        //очистка всяких переменных
        setAdd(0);
        /*
        //проблема! .toArray() занимает больше половины времени работы алгоритма
        SimpleFeatureCollection features = featureSource.getFeatures(CQL.toFilter("ID = '" + idStart + "'"));

        Object[] toArray = features.toArray();
        if (toArray.length == 0) {
        System.out.println("массив 1 пустой");
        return null;
        }
        SimpleFeature featureStart = (SimpleFeature) toArray[0];
         *
         */
        SimpleFeature featureStart = inmemory[(int) idStart - 1];

        /*
        SimpleFeatureCollection features1 = featureSource.getFeatures(CQL.toFilter("ID = '" + idFinish + "'"));

        if (features1.size() == 0) {
        System.out.println("массив 2 пустой");
        return null;
        }
        SimpleFeature featureFinish = features1.features().next();
         *
         */
        SimpleFeature featureFinish = inmemory[(int) idFinish - 1];

        setFeatureStartOld(featureStart);
        setSimpleFeatureStart(splitFeature(new DirectPosition2D(start), featureStart));

        DirectPosition2D finishPoint = new DirectPosition2D(finish);
        setFeatureFinishOld(featureFinish);
        if (getFeatureStartOld().equals(featureFinish)) {
            if (isPointOnGeometry(finishPoint.x, finishPoint.y, (MultiLineString) getSimpleFeatureStart()[0].getDefaultGeometry())) {
                setSimpleFeatureFinish(splitFeature(finishPoint, getSimpleFeatureStart()[0]));
                if (isPointOnGeometry(finishPoint.x, finishPoint.y, (MultiLineString) getSimpleFeatureFinish()[0].getDefaultGeometry())) {
                    setAdd(1);
                } else {
                    setAdd(2);
                }
            } else if (isPointOnGeometry(finishPoint.x, finishPoint.y, (MultiLineString) getSimpleFeatureStart()[1].getDefaultGeometry())) {
                setSimpleFeatureFinish(splitFeature(finishPoint, getSimpleFeatureStart()[1]));
                if (isPointOnGeometry(finishPoint.x, finishPoint.y, (MultiLineString) getSimpleFeatureFinish()[0].getDefaultGeometry())) {
                    setAdd(3);
                } else {
                    setAdd(4);
                }
            }
        } else {
            setSimpleFeatureFinish(splitFeature(finishPoint, featureFinish));
        }



        return routineAlgorithm();
    }

    /**
     * Функция поиска кратчайшего пути.
     * Алгоритм собирает граф из featureSource, simpleFeatureStart[2], simpleFeatureFinish[2]
     * исключая исходные featureStartOld и featureFinishOld.
     *
     * @return Возвращает путь.
     */
    private Path routineAlgorithm() {
        try {
            // get a feature collection somehow
            SimpleFeatureCollection fCollection = inmemoryCollection;
            //create a linear graph generate
            DirectedLineStringGraphGenerator lineStringGen = new DirectedLineStringGraphGenerator();
            //wrap it in a feature graph generator
            MyFeatureGraphGenerator featureGen = new MyFeatureGraphGenerator(lineStringGen);
            //throw all the features into the graph generator
            FeatureIterator iter = fCollection.features();
            /**
             * @author: Александр Линьков
             * Описание: в случае, если точки старта и финиша лежат на одной дуге,
             * необходимо провести разбиение дуги на три части.
             */
            try {
                while (iter.hasNext()) {
                    Feature feature = iter.next();
                    if (feature.equals(featureFinishOld)) {
                        if (add != 0) {
                            if (add == 1) {
                                featureGen.add(simpleFeatureStart[1]);
                                for (int i = 0; i < simpleFeatureFinish.length; i++) {
                                    featureGen.add(simpleFeatureFinish[i]);
                                }
                                simpleFeatureStart[0] = simpleFeatureFinish[0];
                            } else if (add == 2) {
                                featureGen.add(simpleFeatureStart[1]);
                                for (int i = 0; i < simpleFeatureFinish.length; i++) {
                                    featureGen.add(simpleFeatureFinish[i]);
                                }
                                simpleFeatureStart[0] = simpleFeatureFinish[1];
                            } else if (add == 3) {
                                featureGen.add(simpleFeatureStart[0]);
                                for (int i = 0; i < simpleFeatureFinish.length; i++) {
                                    featureGen.add(simpleFeatureFinish[i]);
                                }
                                simpleFeatureStart[1] = simpleFeatureFinish[1];
                            } else if (add == 4) {
                                featureGen.add(simpleFeatureStart[0]);
                                for (int i = 0; i < simpleFeatureFinish.length; i++) {
                                    featureGen.add(simpleFeatureFinish[i]);
                                }
                                simpleFeatureStart[1] = simpleFeatureFinish[0];
                            }
                        } else {
                            for (int i = 0; i < simpleFeatureFinish.length; i++) {
                                featureGen.add(simpleFeatureFinish[i]);
                            }
                        }
                    } else if (feature.equals(featureStartOld)) {
                        for (int i = 0; i < simpleFeatureStart.length; i++) {
                            featureGen.add(simpleFeatureStart[i]);
                        }
                    } else {
                        featureGen.add(feature);
                    }
                }
            } finally {
                iter.close();
            }
            BasicDirectedGraph graph = (BasicDirectedGraph) featureGen.getGraph();
            //find a source node (usually your user chooses one)
            Collection edges = graph.getEdges();
            Node leftNode1 = null;
            Node rightNode1 = null;
            Node leftNode2 = null;
            Node rightNode2 = null;
            Node finishLeftNode1 = null;
            Node finishRightNode1 = null;
            Node finishLeftNode2 = null;
            Node finishRightNode2 = null;
            boolean[] founded2 = new boolean[4];
            for (Iterator e = edges.iterator(); e.hasNext();) {
                Edge edge = (Edge) e.next();
                SimpleFeature feature = (SimpleFeature) edge.getObject();
                if (feature.equals(getSimpleFeatureStart()[0])) {
                    leftNode1 = edge.getNodeA();
                    rightNode1 = edge.getNodeB();
                    founded2[0] = true;
                    if (founded2[0] && founded2[1] && founded2[2] && founded2[3]) {
                        break;
                    }
                } else if (feature.equals(getSimpleFeatureStart()[1])) {
                    leftNode2 = edge.getNodeA();
                    rightNode2 = edge.getNodeB();
                    founded2[1] = true;
                    if (founded2[0] && founded2[1] && founded2[2] && founded2[3]) {
                        break;
                    }
                }
                if (feature.equals(getSimpleFeatureFinish()[0])) {
                    finishLeftNode1 = edge.getNodeA();
                    finishRightNode1 = edge.getNodeB();
                    founded2[2] = true;
                    if (founded2[0] && founded2[1] && founded2[2] && founded2[3]) {
                        break;
                    }
                } else if (feature.equals(getSimpleFeatureFinish()[1])) {
                    finishLeftNode2 = edge.getNodeA();
                    finishRightNode2 = edge.getNodeB();
                    founded2[3] = true;
                    if (founded2[0] && founded2[1] && founded2[2] && founded2[3]) {
                        break;
                    }
                }
            }
            if ((founded2[0] && founded2[1] && founded2[2] && founded2[3]) == false) {
                return null;
            }
            Node start = null;
            Node finish = null;
            if (leftNode1.equals(leftNode2) || leftNode1.equals(rightNode2)) {
                start = leftNode1;
            } else if (leftNode2.equals(rightNode1)) {
                start = leftNode2;
            } else if (rightNode1.equals(rightNode2)) {
                start = rightNode1;
            }
            if (finishLeftNode1.equals(finishLeftNode2) || finishLeftNode1.equals(finishRightNode2)) {
                finish = finishLeftNode1;
            } else if (finishLeftNode2.equals(finishRightNode1)) {
                finish = finishLeftNode2;
            } else if (finishRightNode1.equals(finishRightNode2)) {
                finish = finishRightNode1;
            } // in this case we are using geometry length
            // create a strategy for weighting edges in the graph
            // in this case we are using geometry length
            DijkstraIterator.EdgeWeighter weighter = new DijkstraIterator.EdgeWeighter() {

                @Override
                public double getWeight(Edge e) {
                    SimpleFeature feature = (SimpleFeature) e.getObject();
                    int k = 1;

                    if (feature.getProperty(roadTypeProp).getValue() == null) {
                        System.out.println("property called" + roadTypeProp + " doesn't exist");
                    } else {
                        if (feature.getProperty(roadTypeProp).getValue().toString() == null ? roadTypeProp == null : feature.getProperty(roadTypeProp).getValue().toString().equals("3")) {
                            k = 3;
                        }
                    }
                    if (useRoadQuality) {
                        int quality = 10 - (Integer) feature.getAttribute("QUALITY");
                        k *= 1f + 2f * (double) quality / 5;
                    }
                    Geometry geometry = (Geometry) feature.getDefaultGeometry();
                    return geometry.getLength() * k;
                }
            };
            DijkstraIterator.NodeWeighter nodeWeighter = new DijkstraIterator.NodeWeighter() {

                @Override
                public double getWeight(Node n, Edge e1, Edge e2) {
                    if (memSemaphoresCollection == null) {
                        return 0;
                    }
                    if (useSemaphores) {
                        float time = getSemaphoreTime(n, memSemaphoresCollection);
                        return time * getSemaphoreKoeff();
                    }
                    return 0;
                }
            };
            // Create GraphWalker - in this case DijkstraShortestPathFinder

            DirectedDijkstraIterator dijkstraIterator = new DirectedDijkstraIterator(weighter, nodeWeighter);

            dijkstraIterator.setSource(start);
            if (searchType == 0) {
                DijkstraShortestPathFinder ddspf = new DijkstraShortestPathFinder(graph, dijkstraIterator);
                AStarFunctions asf = new AStarFunctions(finish) {

                    @Override
                    public double cost(AStarNode n1, AStarNode n2) {
                        Edge edge = n1.getNode().getEdge(n2.getNode());
                        SimpleFeature feature = (SimpleFeature) edge.getObject();
                        MultiLineString geometry = (MultiLineString) feature.getDefaultGeometry();
                        Point object = (Point) n2.getNode().getObject();
                        if ((Integer) feature.getProperty(onewayProp).getValue() == 1) {
                            if (geometry.getCoordinates()[0].equals(object.getCoordinate())) {
                                return Double.MAX_VALUE;
                            }
                        }
                        if (useSemaphores) {
                            float time1 = getSemaphoreTime((Node) n1, memSemaphoresCollection);
                            float time2 = getSemaphoreTime((Node) n2, memSemaphoresCollection);
                            return (time1 + time2) * getSemaphoreKoeff();
                        }
                        int k = 1;
                        if (feature.getProperty(roadTypeProp).getValue().toString().equals("3")) {
                            k = 3;
                        }

                        Coordinate coordinate1 = ((Point) n1.getNode().getObject()).getCoordinate();
                        Coordinate coordinate2 = ((Point) n2.getNode().getObject()).getCoordinate();
                        return coordinate1.distance(coordinate2) * k;
                    }

                    @Override
                    public double h(Node n) {
                        Coordinate coordinate1 = ((Point) n.getObject()).getCoordinate();
                        Coordinate coordinate2 = ((Point) this.getDest().getObject()).getCoordinate();
                        return coordinate1.distance(coordinate2);
                    }
                };

                switch (algorithm) {
                    case ASTAR:
                        AStarShortestPathFinder astar = new AStarShortestPathFinder(graph, start, finish, asf);
                        astar.calculate();
                        return astar.getPath();
                    case DIJKSTRA:
                        ddspf.calculate();
                        return ddspf.getPath(finish);
                }
            }

        } catch (Exception ex) {
            Logger.getLogger(Guide.class.getName()).log(Level.SEVERE, null, ex);
        }
        return null;
    }

    private float getSemaphoreTime(Node node, SimpleFeatureCollection semaphoresCollection) {
        Point point = (Point) node.getObject();
        FilterFactory factory = FilterFactoryFinder.createFilterFactory();
        PropertyName the_geom = factory.property(semaphoresCollection.getSchema().getGeometryDescriptor().getName());
        LiteralExpression geomExpression = factory.createLiteralExpression(point);
        Filter filter = factory.intersects(the_geom, geomExpression);
        SimpleFeatureCollection features = semaphoresCollection.subCollection(filter);
        if (features.size() == 0) {
            return 0;
        } else {
            SimpleFeatureIterator iterator = features.features();
            while (iterator.hasNext()) {
                SimpleFeature next = iterator.next();
                Long time = (Long) next.getAttribute(timeProp);
                return time;
            }
        }
        return 0;
    }

    public enum GeomType {

        POINT, LINE, POLYGON
    };

    /**
     * Retrieve information about the feature geometry
     */
    private void setGeometry(FeatureSource source) {
        // !Внимание! переделать
        GeometryDescriptor geomDesc = source.getSchema().getGeometryDescriptor();
        geometryAttributeName = geomDesc.getLocalName();

        Class<?> clazz = geomDesc.getType().getBinding();

        if (Polygon.class.isAssignableFrom(clazz)
                || MultiPolygon.class.isAssignableFrom(clazz)) {
            geometryType = GeomType.POLYGON;

        } else if (LineString.class.isAssignableFrom(clazz)
                || MultiLineString.class.isAssignableFrom(clazz)) {

            geometryType = GeomType.LINE;

        } else {
            geometryType = GeomType.POINT;
        }
    }

    /**
     * Возвращает SimpleFeatureType из коллекции
     */
    public SimpleFeatureType getSchema() {
        if (inmemoryCollection.getSchema() != null) {
            return inmemoryCollection.getSchema();
        }
        return null;
    }

    public SimpleFeature[] getInmemory() {
        return inmemory;
    }

    private SimpleFeatureCollection getInmemoryCollection() {
        return inmemoryCollection;
    }

    public String getOnewayProp() {
        return onewayProp;
    }

    public void setOnewayProp(String onewayProp) {
        this.onewayProp = onewayProp;
    }

    public String getRoadTypeProp() {
        return roadTypeProp;
    }

    public void setRoadTypeProp(String roadTypeProp) {
        this.roadTypeProp = roadTypeProp;
    }

    public String getTimeProp() {
        return timeProp;
    }

    public void setTimeProp(String timeProp) {
        this.timeProp = timeProp;
    }

    public void dispose()
    {
        
    }
}
